๐Ÿ“‚ Array vs. ArrayList vs. LinkedList

@Seongukbaek Posted May 19, 2022 ยท Updated May 19, 2022 ยท 3 min read

๐Ÿงท ์„ธ ์ž๋ฃŒ ๊ตฌ์กฐ

  • Array : index๋กœ ๋น ๋ฅด๊ฒŒ ๊ฐ’์„ ์ฐพ๋Š” ๊ฒƒ์ด ๊ฐ€๋Šฅ
  • LinkedList : ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ๊ฐ€ ๋น ๋ฆ„
  • ArrayList : ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๋Š” ๊ฒƒ์€ ๋น ๋ฅด์ง€๋งŒ, ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ๊ฐ€ ๋А๋ฆผ

๐Ÿชš ๋” ์ž์„ธํ•œ ๋น„๊ต

Array

  • ์„ ์–ธํ•  ๋•Œ ํฌ๊ธฐ์™€ ๋ฐ์ดํ„ฐ ํƒ€์ž…์„ ์ง€์ •ํ•ด์•ผ ํ•œ๋‹ค.
  • ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์‚ฌ์šฉํ•  ์‚ฌ์ด์ฆˆ๋ฅผ ๋ฏธ๋ฆฌ ํ• ๋‹นํ•ด๋‘๊ณ  ์‚ฌ์šฉํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋‹ค.

    • ๋”ฐ๋ผ์„œ ๊ณ„์† ๋ฐ์ดํ„ฐ๊ฐ€ ๋Š˜์–ด๋‚  ๊ฒฝ์šฐ, ์ตœ๋Œ€ ์‚ฌ์ด์ฆˆ๋ฅผ ์•Œ ์ˆ˜ ์—†์„ ๋•Œ ์‚ฌ์šฉํ•˜๊ธฐ๋Š” ๋ถ€์ ํ•ฉํ•˜๋‹ค.
    • ๋˜ํ•œ ์ค‘๊ฐ„์— ๋ฐ์ดํ„ฐ๋ฅผ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œํ•˜๋Š” ๊ฒƒ๋„ ๋งค์šฐ ๋น„ํšจ์œจ์ ์ด๋‹ค. (์ ‘๊ทผํ•˜์—ฌ ์‚ญ์ œํ•œ ๋’ค, ๋‚˜๋จธ์ง€ ๋’ท ๋ฐ์ดํ„ฐ๋“ค์„ shift ํ•ด์ฃผ๋Š” ๋น„์šฉ์œผ๋กœ ์ธํ•ด ์ตœ์•…์˜ ๊ฒฝ์šฐ O(N)O(N))
    • ๋Œ€์‹ , index ๋ฅผ ํ†ตํ•ด ๊ฒ€์ƒ‰์„ O(1)O(1)์— ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์žฅ์ ์ด ์žˆ๋‹ค.

List

  • Array ์ฒ˜๋Ÿผ ํฌ๊ธฐ๋ฅผ ์ง€์ •ํ•˜์ง€ ์•Š์•„๋„ ๋œ๋‹ค.
  • ํ•˜์ง€๋งŒ Array ์—์„œ index ๊ฐ€ ์ค‘์š”ํ–ˆ๋˜ ๊ฒƒ์ฒ˜๋Ÿผ, List ์—์„œ๋Š” ์ˆœ์„œ๊ฐ€ ์ค‘์š”ํ•˜๋‹ค.

    • ํฌ๊ธฐ๊ฐ€ ์ •ํ•ด์ ธ์žˆ์ง€ ์•Š์•„ ์ค‘๊ฐ„์— ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž…์ด๋‚˜ ์‚ญ์ œ๊ฐ€ ๋ฐœ์ƒํ•ด๋„ Array ๋ณด๋‹ค๋Š” ๋œ ๋น„ํšจ์œจ์ ์ด๋‹ค.
    • ๋˜ํ•œ index ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๊ธฐ์— ๊ฒ€์ƒ‰ ๋˜ํ•œ ๋น ๋ฅด๋‹ค.
    • ํ•˜์ง€๋งŒ ์ค‘๊ฐ„์— ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ ์‹œ ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋Š” ๋‹จ์ ์ด ์žˆ๋‹ค. (์‚ฝ์ž… ๋ฐ ์‚ญ์ œ ์‹œ ์ค„์ค„์ด ๋‹น๊ฒจ์ง€๊ฑฐ๋‚˜, ๋ฐ€๋ ค๋‚  ๋•Œ ์ˆ˜ํ–‰๋˜๋Š” ์—ฐ์‚ฐ์ด ์ถ”๊ฐ€๋˜๊ณ , ๋ฉ”๋ชจ๋ฆฌ ๋˜ํ•œ ๋‚ญ๋น„๋œ๋‹ค.)

LinkedList

  • ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์—๋Š” ๋‹จ์ผ, ๋‹ค์ค‘ ๋“ฑ์ด ์กด์žฌํ•œ๋‹ค. ๋ฌด์Šจ ์ข…๋ฅ˜๋“ , ํ•œ ๋…ธ๋“œ์— ์—ฐ๊ฒฐ๋  ๋…ธ๋“œ์˜ ํฌ์ธํ„ฐ ์œ„์น˜๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ฐฉ์‹์ด๋‹ค.

๋‹จ์ผ์€ ๋’ท ๋…ธ๋“œ๋งŒ ๊ฐ€๋ฆฌํ‚ค๊ณ , ๋‹ค์ค‘์€ ์•ž๋’ค ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ ๊ฐ€๋ฆฌํ‚จ๋‹ค.

  • ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ๋ฅผ ํ•˜๋”๋ผ๋„, ์ „์ฒด๋ฅผ ๋Œ์ง€ ์•Š๊ณ  ์ด์ „ ๊ฐ’๊ณผ ๋‹ค์Œ ๊ฐ’์ด ๊ฐ€๋ฅดํ‚ค๊ณ  ์žˆ๋˜ ์ฃผ์†Œ ๊ฐ’๋งŒ ์ˆ˜์ •ํ•ด ์—ฐ๊ฒฐ์‹œํ‚ด์œผ๋กœ์จ ๋น ๋ฅธ ์ˆ˜ํ–‰์ด ๊ฐ€๋Šฅํ•˜๋‹ค.
  • ํ•˜์ง€๋งŒ, k ๋ฒˆ์งธ ๊ฐ’์„ ์ฐพ๋Š” ๋ฌธ์ œ์—์„œ๋Š” ๋น„ํšจ์œจ์ ์ด๋‹ค.

    • ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์—์„œ๋Š” index ๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์—, ์ˆœ์ฐจ ๊ฒ€์ƒ‰์„ ์ˆ˜ํ–‰ํ•˜๋ฏ€๋กœ ์‹œ๊ฐ„์ด ๋” ๊ฑธ๋ฆฐ๋‹ค.
  • ๊ฒฐ๊ณผ์ ์œผ๋กœ, ๊ฒ€์ƒ‰๊ณผ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ์— ๋Œ€ํ•ด์„œ O(N)O(N)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

    • ํ•˜์ง€๋งŒ, Tree ๊ตฌ์กฐ์˜ ๊ทผ๊ฐ„์ด ๋˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋กœ, Tree ์—์„œ ์‚ฌ์šฉ๋˜์—ˆ์„ ๋•Œ ์œ ์šฉํ•˜๋‹ค.

์ƒํ™ฉ์— ๋งž๊ฒŒ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ž˜ ์„ ํƒํ•˜๋Š” ๋Šฅ๋ ฅ์ด ์ค‘์š”ํ•˜๋‹ค.


๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€